\documentclass{ctexart}

\usepackage{geometry}%设置页面大小边距等
\usepackage{authblk}%作者机构等信息
\usepackage{graphicx}%插入图片
\usepackage{amssymb}%为了用\mathbb
\usepackage{amsmath}%数学方程的显示
\usepackage{listings}%插入代码
\usepackage{fancyhdr}%设置页眉页脚
\usepackage{lastpage}%总页数
\usepackage{tikz}
\usepackage{listings}%插入代码
\usepackage{hyperref}%引用网页
\usepackage{xcolor}%实现代码颜色高亮
\lstset{frame=single,basicstyle=\ttfamily,columns=flexible,language={C},
keywordstyle=\bf\color{blue},
commentstyle=\it\color[RGB]{0,96,96},
numberstyle=\color[RGB]{0,192,192}}

\geometry{a4paper,left=2cm,right=2cm,top=2cm,bottom=2cm}%一定要放在前面！

\pagestyle{fancy}%设置页眉页脚
\lhead{陈冠宇\ 3200102033}%页眉左
\chead{Numerical Analysis}%页眉中
\rhead{HW3}%章节信息
\cfoot{\thepage/\pageref{LastPage}}%当前页，记得调用前文提到的宏包
\rfoot{School of Mathematical Sciences in ZJU}
\renewcommand{\headrulewidth}{0.1mm}%页眉线宽，设为0可以去页眉线
\renewcommand{\footrulewidth}{0.1mm}%页脚线宽，设为0可以去页眉线
\setlength{\headwidth}{\textwidth}

\newtheorem{theorem}{Theorem}
\newtheorem{proof}{Proof}
\newtheorem{solution}{Solution:}

\hypersetup{%设置网页链接颜色等
    colorlinks=true,%链接将会有颜色，默认是红色
    urlcolor=blue,%链接到网站的链接将会变为蓝绿色（cyan）
    }

\title{Theoretical questions of Chapter2}
\begin{document}
\section*{Theoretical questions of Chapter2}
\subsection*{\uppercase\expandafter{\romannumeral1}}
\begin{solution}.\\
(1)By Lagrange formula, we have $$P_1(x)=f_0l_0(x)+f_1l_1(x),$$
where $l_0(x)=\frac{x-2}{1-2}=2-x,l_1(x)=\frac{x-1}{2-1}=x-1,f_0=1,f_1=\frac{1}{2}$.

Then we have $$P_1(x)=2-x+\frac{1}{2}(x-1)=-\frac{x}{2}+\frac{3}{2}$$

Since $$f(x)-p_1(f;x)=\frac{f''(\xi (x))}{2}(x-x_0)(x-x_1),$$

then $$\frac{1}{x}-(-\frac{x}{2}+\frac{3}{2})=\xi^{-3}(x)(x-1)(x-2)$$

That is $$\xi(x)=\sqrt[3]{2x}$$
(2)Since $\xi(x)=\sqrt[3]{2x}$ is monotonic increasing in $[1,2]$, then
$$\max{\xi(x)}=\xi(2)=\sqrt[3]{4},\quad \min{\xi(x)=\xi(1)=\sqrt[3]{2}}.$$

Since $f''(\xi(x))=\frac{1}{x},$ which is monotonic decreasing in $[1,2]$,

then $$\max{f''(\xi(x))}=1$$
\end{solution}

\subsection*{\uppercase\expandafter{\romannumeral2}}
\begin{solution}
  Let $q(x)$ be the unique polynomial interpolation, such that $q(x_i)=\sqrt{f_i}$. Then we let $p(x_i) = q(x_i)^2 = f_i$ and have $q(x)\in \mathbb{P}_n$. Then $p(x)\in \mathbb{P}_{2n}$.

  By Lagrange formula, $$q(x)=\sum_{i=0}^{n}\sqrt{f_i}\prod_{i=0,i\neq k}^{n}\frac{x-x_i}{x_k-x_i}$$

  That is $$p(x)=\left(\sum_{i=0}^{n}\sqrt{f_i}\prod_{i=0,i\neq k}^{n}\frac{x-x_i}{x_k-x_i}\right)^2$$
\end{solution}

\subsection*{\uppercase\expandafter{\romannumeral3}}
\begin{solution}(1)\\
When $n=1$,we have $f[t,t+1]=e^{t}-e^{t-1}=\frac{e-1}{e}e^t.$

Assume n = k, $$f[t,t+1,\cdots ,t+k]=\frac{(e-1)^k}{k!}e^t,$$
then$$f[t+1,t+2,\cdots,t+1+k]=\frac{(e-1)^k}{k!}e^{t+1}$$
then when n = k+1, we have
\begin{equation*}
  \begin{aligned}
   f[t,t+1,\cdots,t+k+1]&=\frac{f[t+1,t+2,\cdots,t+1+k]-f[t,t+1,\cdots ,t+k]}{(t+k+1-t)}\\
   &=\frac{(e-1)^k}{k!}e^t(e-1)/(k+1)\\
   &=\frac{(e-1)^{k+1}}{(k+1)!}e^t
  \end{aligned}
\end{equation*}
By induction, $\forall t\in \mathbb{R},f[t,t+1,\cdots,t+n]=\frac{(e-1)^n}{n!}e^t$\\
(2)Let t = 0, then by the conclusion above, we have
\begin{equation*}
  \begin{aligned}
  f[0,1,\cdots, n]&=\frac{(e-1)^n}{n!}=\frac{f^{(n)(\xi)}}{n!}\\
  &= e^\xi
  \end{aligned}
\end{equation*}
That is $e^\xi =(e-1)^n.$

Then we have $\xi = n \ln (e-1)\geq \frac{n}{2}$.that is $\xi$ located to the right of the midpoint.
\end{solution}
\subsection*{\uppercase\expandafter{\romannumeral4}}
\begin{solution}(1)\\
Since we have
$$\begin{array}{ccccc}
  x & 0 & 1 & 3 & 4 \\
  f(x) & 5 & 3 & 5 & 12
\end{array}$$
we can construct the following table of divided difference
$$\begin{array}{ccccccc}
  0 & | & 5 &   &   &   &   \\
  1 & | & 3 & -2 &   &   &   \\
  3 & | & 5 & 1 & 1 &   &   \\
  4 & | & 12 & 7 & 2 & 1/4 &   \\
\end{array}$$
then we obtain $$p_3(f;x)=5-2x+x(x-1)+\frac{1}{4}x(x-1)(x-3)=\frac{1}{4}x^3-\frac{9}{4}x+5$$
(2)Let $p'_3=\frac{3}{4}x^2-\frac{9}{4}=0$, then $x = \pm \sqrt{3}.$

Then when $x\in (1,\sqrt{3})$,p is monotonic decreasing, while $x\in (\sqrt{3},3)$, p is increasing. That is $f_{min}=p(\sqrt{3})=5-\frac{3\sqrt{3}}{2}\approx 2.402$ and $x_{min}\approx 1.732$
\end{solution}
\subsection*{\uppercase\expandafter{\romannumeral5}}
\begin{solution}(1)
  Since $f=x^7$, then the table of divided differences has the form
  $$\begin{array}{cccccccc}
      0 & | & 0 &   &   &   &   &   \\
      1 & | & 1 & 1 &   &   &   &   \\
      1 & | & 1 & 7 & 6 &   &   &   \\
      1 & | & 1 & 7 & 21 & 15 &   &   \\
      2 & | & 128 & 127 & 120 & 99 & 42 &   \\
      2 & | & 128 & 448 & 321 & 201 & 102 &  30
    \end{array}$$
    Then $f(0,1,1,1,2,2)=30$\\
(2)Let $f^{(5)}(x)=2520x^2=30$, then $x=\frac{1}{2\sqrt{21}}\approx 0.1091$

\end{solution}
\subsection*{\uppercase\expandafter{\romannumeral6}}
\begin{solution}
(1)We can obtain the table of divided differences
$$\begin{array}{ccccccc}
    0 & | & 1 &   &   &   &   \\
    1 & | & 2 & 1 &   &   &   \\
    1 & | & 2 & -1 & -2 &  &  \\
    3 & | & 0 & -1 & 0 & 2/3 & \\
    3 & | & 0 & 0 & 1/2 & 1/4 & -5/36
  \end{array}$$
  Then $$p(x)=1+x-2x(x-1)+\frac{2}{3}x(x-1)^2-\frac{5}{36}x(x-1)^2(x-3)$$

  Hence $f(2) \approx p(2)= \frac{11}{18}$\\
(2)Since $N = 2+1+1 = 4$, then by Thm 2.37 we have
$$\begin{aligned}
f(x)-p_5(f;x)&=\frac{f^{(N+1)}(\xi)}{(N+1)!}\prod_{i=0}^{k}(x-x_i)^{m_i+1}\\
&=\frac{f^{(5)}(\xi)}{5!}x(x-1)^2(x-3)^2
\end{aligned}$$
Hence, $f(2)-p(2)\leq \frac{M}{60}$
\end{solution}
\subsection*{\uppercase\expandafter{\romannumeral7}}
\begin{solution}
    By Thm 2.29 we has have $$f[x_0,x_1,\cdots ,x_k]=\frac{\triangle^{k}f_0}{k!h^k}$$
    That is $$\triangle^{k}f(x_0)=k!h^kf[x_0,x_1,\cdots,x_n]$$
    Since $\triangle^nf_i=\nabla^nf_{i+n}$ by Thm 2.27 and $f[x_0,x_1,\cdots,x_k]=f[x_{i_0},x_{i_1},\cdots,x_{i_k}]$ by Corollary 2.15.
    \\
    Hence
    $$\begin{aligned}
    k!h^kf[x_0,x_{-1},\cdots,x_{-k}]&=k!h^kf[x_{-k},\cdots,x_{0}]\\
    &=\triangle^{k}f(x_{-k})\\
    &=\nabla^kf(x_0)
    \end{aligned}.$$
\end{solution}
\subsection*{\uppercase\expandafter{\romannumeral8}}
\begin{proof}
  Proof by induction.

  When n=1, $$\begin{aligned}
  \frac{\partial f[x_0,x_1]}{\partial x_0}
  &=\frac{\partial}{\partial x_0}\left(\frac{f[x_1]-f[x_0]}{x_1-x_0}\right)\\
  &=\frac{-f'(x_0)(x_1-x_0)+f(x_1)-f(x_0)}{(x_1-x_0)^2}\\
  &=\frac{f[x_1,x_0]-f'[x_0]}{x_1-x_0}\\
  &=f[x_0,x_0,x_1]
  \end{aligned}$$
  Assume the induction holds for n-1. That is
  $$\frac{\partial f[x_0,\cdots,x_{n-1}]}{\partial x_0}=f[x_0,x_0,\cdots,x_{n-1}]$$
  Then we consider n:
  \begin{equation*}
    \begin{aligned}
        \frac{\partial f[x_0,x_1,\cdots,x_n]}{\partial x_0}&=
        \frac{\partial}{\partial x_0}\left( \frac{f[x_1, \cdots, x_n]-f[x_0, x_1, \cdots, x_n]}{x_n-x_0}\right)\\
        &=\frac{-\frac{\partial f[x_0,\cdots,x_{n-1}]}{\partial x_0}(x_n-x_0)+\frac{f[x_1, \cdots, x_n]-f[x_0, x_1, \cdots, x_n]}{x_n-x_0}}{(x_n-x_))^2}\\
        &=\frac{f[x_0,x_1,\cdots,x_n]-f[x_0,x_0,x_1,\cdots,x_{n-1}]}{x_n-x_0)}\\
        &=f[x_0,x_0,x_1,\cdots,x_n]
    \end{aligned}
  \end{equation*}

\end{proof}

\subsection*{\uppercase\expandafter{\romannumeral9}}
\begin{solution}
Note the polynomial $a_0x^n+a_1x^{n-1}+\cdots+a_n=p(x)$.\\
Since $x\in [a,b]$, then let $t=\frac{2x-(a+b)}{b-a}\in [-1,1]$,That is $x = \frac{(b-a)t+(a+b)}{2}$.\\
Then we have $p(x)=p\left(\frac{(b-a)t+(a+b)}{2}\right)=q(t)$.
Also let $\tilde{\mathbb{Q}}_n=\{q(t)|a_i\in \mathbb{R},i\neq 0, t\in [-1,1]\}$\\
Then by Chebyshev Thm, we have
$$\forall q\in \tilde{\mathbb{Q}}_n,\ \max_{t\in [-1,1]}\left|\frac{T_n(t)}{2^{n-1}}\right|\leq \max_{[-1,1]}\left|\frac{q(t)}{a_0(\frac{b-a}{2})^n}\right|,\ where\ t=\frac{2x-(a+b)}{b-a}\in [-1,1],\ x\in [a,b]$$
That is $$\max_{t\in[-1,1]}\left|q(t)\right|=\max_{x\in[a,b]}\left|p(x)\right|\geq \frac{a_0}{2^{n-1}}(\frac{b-a}{2})^n$$

Then $min=\frac{|a_0|}{2^{n-1}}(\frac{b-a}{2})^n$
\end{solution}
\subsection*{\uppercase\expandafter{\romannumeral10}}
\begin{proof}
    Since we know that $||\hat{p}_n||_\infty=\frac{1}{|T_n(a)|.}$, and
    $$\hat{p}_n(x)(x'_k)=\frac{(-1)^k}{T_n(a)},\quad where \quad x'_k=cos(\frac{k}{n}\pi),k=0,1,\cdots,n$$\\
    Suppose that:$$\exists p\in \mathbb{P}^a_n,\ s.t.\ ||p||_\infty < \frac{1}{|T_n(a)|.}$$
    Let $q(x)=p(x)-\hat{p}_n(x)\in \mathbb{P}_n,$,then $q(a)=0.$ And
    $$q(x'_k)=p(x'_k)-\frac{(-1)^k}{T_n(a)},k=0,1,\cdots,n$$
    Hence $$q(x'_k)q('_{k+1})<0$$
    Then we have $$\exists \xi_1,\cdots,\xi_n,s.t.q(\xi_1)=\cdots=q(\xi_n)=0$$
    However, q(a)=0 and a>1 shows that q has at least n+1 zero points.\\
    Contradiction.
\end{proof}
\subsection*{\uppercase\expandafter{\romannumeral11}}
\begin{proof}
  (1)Since $t\in (0,1)$, then $b_{n,k}(t)>0.$\\
  (2)We have $$\begin{aligned}
  1=(t+1-t)^n&=\sum_{k=0}^{n}C^k_nt^k(1-t)^{n-k}=\sum_{k=0}^{n}b_{n.k}(t)
  \end{aligned}$$\\
  (3)Since we have $kC^k_n=nC^{k-1}_{n-1},$ then $$\begin{aligned}
  \sum_{k=0}^{n}kb_{n,k}(t)&=\sum_{k=0}^{n}kC^k_nt^k(1-t)^{n-k}\\
  &=n\sum_{k=1}^{n}kC^{k-1}_{n-1}t^k(1-t)^{n-k}\\
  &=nt\sum_{k=1}^{n}kC^{k-1}_{n-1}t^{k-1}(1-t)^{n-k}\\
  &=nt\sum_{k=0}^{n-1}C^k_nt^k(1-t)^{n-k}=nt
  \end{aligned}$$\\
  (4)Apply (3) to this, we have:
  $$\begin{aligned}
  \sum_{k=0}^{n}(k-nt)^2b_{(n,k)}(t)
  &=\sum_{k=0}^{n}k^2b_{(n,k)}-2nt\sum_{k=0}^{n}kb_{(n,k)}+(nt)^2\sum_{k=0}^{n}b_{(n,k)}\\
  &=nt\sum_{k=1}^{n}k\frac{(n-1)!}{(k-1)!(n-k)!}t^{k-1}(1-t)^{n-k}-2(nt)^2+(nt)^2\\
  &=nt\sum_{k=0}^{n-1}(k+1)C^k_{n-1}t^k(1-t)^{n-1-k}-(nt)^2\\
  &=nt\left(\sum_{k=0}^{n-1}kC^k_{n-1}t^k(1-t)^{n-1-k}
  +\sum_{k=0}^{n-1}C^k_{n-1}t^k(1-t)^{n-1-k}\right)-(nt)^2\\
  &=nt(n-1)t+nt-(nt)^2\\
  &=nt(1-t)
  \end{aligned}$$
\end{proof}
\end{document} 